package binTree;
//236. 二叉树的最近公共祖先
public class Num236_lowestCommonAncestor {
    //存储祖先
    private TreeNode lca;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //找祖先
        findNode(root,p,q);
        return lca;
    }

    private boolean findNode(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null){
            return false;
        }
        //现在左子树中寻找
        int left = findNode(root.left , p , q) ? 1 : 0;
        int right = findNode(root.right , p ,q) ? 1 : 0;
        int mid = (root == q || root == p) ? 1 : 0;
        //找到最近公共祖先
        if (left + right + mid == 2){
            lca = root;
        }
        return (left + right +mid) > 0;
    }
}
